%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{tabular}{ll} \hline
Implementation & Time complexity \\\hline
list           & $O(n^2)$ \\[4pt]
binary heap    & $O \big( (n + m) \ln n \big)$ \\[4pt]
$k$-ary heap   & $O \big( (kn + m) \frac{\ln n}{\ln k} \big)$ \\[4pt]
Fibonacci heap & $O(n \ln n + m)$ \\\hline
\end{tabular}
